public class MaxProduct {
    // leetcode 乘积最大的子数组
    // https://leetcode.cn/problems/maximum-product-subarray/description/?envType=study-plan-v2&envId=top-100-liked
    public int maxProduct(int[] nums) {
        // dp[0]表示以i元素为结尾的正数最大的乘积，dp[1]表示以i元素为结尾的负数最小的乘积
        int n = nums.length;
        int[][] dp = new int[2][n+1];
        dp[0][0] = 1;
        dp[1][0] = 1;
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            if(nums[i-1] > 0) {
                dp[0][i] = Math.max(nums[i-1], dp[0][i-1] * nums[i-1]);
                dp[1][i] = Math.min(nums[i-1], dp[1][i-1] * nums[i-1]);
            }else {
                dp[0][i] = Math.max(nums[i-1], dp[1][i-1] * nums[i-1]);
                dp[1][i] = Math.min(nums[i-1], dp[0][i-1] * nums[i-1]);
            }
            ret = Math.max(Math.max(dp[0][i], dp[1][i]), ret);
        }
        return ret;
    }
}
